/*
 *  Copyright 2007-2008 by Matthias Buch-Kromann <mbk.isv@cbs.dk>.
 *  *
 *  This file is part of the Open-source Dependency Toolkit (OSDT),
 *  see http://code.google.com/p/open-source-dependency-toolkit.
 *  
 *  The OSDT is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as 
 *  published by the Free Software Foundation, either version 3 of 
 *  the License, or (at your option) any later version.
 * 
 *  The OSDT is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public 
 *  License along with the OSDT in the files COPYING and COPYING.LESSER.
 *  If not, see http://www.gnu.org/licenses.
 */

package org.osdtsystem.graphs.views;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.osdtsystem.exceptions.IllegalCycleException;
import org.osdtsystem.exceptions.IllegalOrderException;
import org.osdtsystem.exceptions.InconsistentGraphException;
import org.osdtsystem.exceptions.InconsistentViewException;
import org.osdtsystem.exceptions.LayerNotFoundException;
import org.osdtsystem.exceptions.LocationNotFoundException;
import org.osdtsystem.exceptions.NodeNotFoundException;
import org.osdtsystem.exceptions.NonUniqueNameException;
import org.osdtsystem.exceptions.OsdtSyntaxException;
import org.osdtsystem.graphs.Graph;
import org.osdtsystem.graphs.io.GraphIDs;
import org.osdtsystem.values.EdgeID;
import org.osdtsystem.values.Layer;
import org.osdtsystem.values.NodeID;
import org.osdtsystem.values.StringFeature;

/**
 * A projective tree. 
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public class ProjectiveTreeEngine extends TreeEngine implements ProjectiveTree {
    private Layer siblingLayer;
    
    final static StringFeature RelationNextLeftField = new StringFeature("nleft");
    final static StringFeature RelationNextRightField = new StringFeature("nright");
    final static StringFeature RelationOuterLeftChild = new StringFeature("oleft");
    final static StringFeature RelationInnerLeftChild = new StringFeature("ileft");
    final static StringFeature RelationInnerRightChild  = new StringFeature("iright");
    final static StringFeature RelationOuterRightChild  = new StringFeature("oright");

    
    /**
     * Construct a new projective tree for the given graph, node collection, 
     * and top node, and use the given name as a base name when naming
     * the layers needed to store the tree.
     * @param graph the underlying graph
     * @param nodeCollection the underlying node collection
     * @param top the top node in the node collection
     * @param name the base name used to name new tree layers
     * @throws NonUniqueNameException 
     */
    public ProjectiveTreeEngine(Graph graph, NodeCollection nodeCollection, NodeID top, String name) 
            throws NonUniqueNameException {
        super(graph, nodeCollection, top, name);
        try {
            siblingLayer = graph.addLayer(name + ViewConstants.SiblingSuffix);
            graph.addLayerFeature(siblingLayer, ViewConstants.EdgeRelationFeature);
        } catch (LayerNotFoundException ex) {
            throw new InconsistentViewException(
                    "Inconsistent ProjectiveTreeEngine: sibling layer not found", ex);
        }
    }
    
    public ProjectiveTreeEngine(Graph graph, NodeCollection nodeCollection, NodeID top, Layer treeLayer, 
            Layer siblingLayer) {
        super(graph, nodeCollection, top, treeLayer);
        this.siblingLayer = siblingLayer;
    }

    @Override
    public EdgeID moveSubtree(NodeID child, NodeID parent, int position, Object relation) 
            throws NodeNotFoundException, IllegalCycleException {
        // Return if position is zero
        if (position == 0)
            return null;
        
        // Set the new parent in the underlying tree
        EdgeID edge;
        try {
            edge = super.setParent(child, parent, relation);
        } catch (IllegalOrderException ex) {
            throw new InconsistentViewException("Unexpected illegal order exception in moveSubtree");
        }

        // If we survived this far, the underlying new tree is ok (in particular,
        // it is acyclic). First unlink subroot from its current parent and 
        // siblings in the sibling structure.
        unlinkFromSiblings(child);
        
        // Now attach subroot to its new position in the siblings structure
        NodeID leftSibling = null;
        NodeID rightSibling = null;
        if (position > 0) {
            // Node is inserted in the right field (after parent)
            rightSibling = innerRightChild(parent);
            
            // Move to desired position
            while (position > 1 && rightSibling != null) {
                --position;
                leftSibling = rightSibling;
                rightSibling = rightSibling(leftSibling);
            }
                
            // Modify siblings tree
            if (leftSibling != null && rightSibling == null) {
                // Node is inserted at the end of the right field
                graph().removeEdge(firstEdgeMatch(
                        graph().inEdges(leftSibling, siblingLayer),
                        RelationOuterRightChild));
                addSiblingEdge(child, parent, RelationOuterRightChild);
                addSiblingEdge(child, leftSibling, RelationNextRightField);
            } else if (leftSibling != null && rightSibling != null) {
                // Node is inserted in the middle of the right field
                graph().removeEdge(firstEdgeMatch(
                        graph().inEdges(rightSibling, siblingLayer),
                        RelationNextRightField));
                addSiblingEdge(child, leftSibling, RelationNextRightField);
                addSiblingEdge(rightSibling, child, RelationNextRightField);
            } else if (leftSibling == null && rightSibling != null) {
                // Node is inserted at the beginning of the right field
                graph().removeEdge(firstEdgeMatch(
                        graph().inEdges(rightSibling, siblingLayer),
                        RelationInnerRightChild));
                addSiblingEdge(child, parent, RelationInnerRightChild);
                addSiblingEdge(rightSibling, child, RelationNextRightField);
            } else if (leftSibling == null && rightSibling == null) {
                // Node is the only node in the right field
                addSiblingEdge(child, parent, RelationInnerRightChild);
                addSiblingEdge(child, parent, RelationOuterRightChild);
            }
        } else {
            // Node is inserted in the left field (before parent)
            leftSibling = innerLeftChild(parent);
            
            // Move to desired position
            while (position < -1 && leftSibling != null) {
                ++position;
                rightSibling = leftSibling;
                leftSibling = leftSibling(rightSibling);
            }
                
            // Modify siblings tree
            if (leftSibling != null && rightSibling == null) {
                // Node is inserted at the end of the left field
                graph().removeEdge(firstEdgeMatch(
                        graph().inEdges(leftSibling, siblingLayer),
                        RelationInnerLeftChild));
                addSiblingEdge(child, parent, RelationInnerLeftChild);
                addSiblingEdge(child, leftSibling, RelationNextLeftField);
            } else if (leftSibling != null && rightSibling != null) {
                // Node is inserted in the middle of the left field
                graph().removeEdge(firstEdgeMatch(
                        graph().inEdges(rightSibling, siblingLayer),
                        RelationNextLeftField));
                addSiblingEdge(child, leftSibling, RelationNextLeftField);
                addSiblingEdge(rightSibling, child, RelationNextLeftField);
            } else if (leftSibling == null && rightSibling != null) {
                // Node is inserted at the beginning of the left field
                graph().removeEdge(firstEdgeMatch(
                        graph().inEdges(rightSibling, siblingLayer),
                        RelationOuterLeftChild));
                addSiblingEdge(child, parent, RelationOuterLeftChild);
                addSiblingEdge(rightSibling, child, RelationNextLeftField);
            } else if (leftSibling == null && rightSibling == null) {
                // Node is the only node in the right field
                addSiblingEdge(child, parent, RelationInnerLeftChild);
                addSiblingEdge(child, parent, RelationOuterLeftChild);
            }
        }
        
        // Return the edge from the tree
        return edge;
    }


    @Override
    public EdgeID setParent(NodeID child, NodeID parent, Object relation) 
            throws NodeNotFoundException, IllegalCycleException, IllegalOrderException {
        // Find projective insertion position at new parent (after unlinking old)
        int position = projectiveParentSite(child, parent);
        
        // Throw exception if the position is illegal
        if (position == 0)
            throw new IllegalOrderException("Child node " + child 
                    + " cannot attach projectively to parent " + parent);
        
        // Otherwise make attachment
        return moveSubtree(child, parent, position, relation);   
    }
        
    @Override
    public NodeID addNode(NodeID parent, Object relation) 
            throws NodeNotFoundException {
        return addNode(parent, rightChildren(parent) + 1, relation);
    }

    @Override
    public NodeID addNode(NodeID parent, int position, Object relation) 
            throws NodeNotFoundException {
        // Create new child node in unordered tree
        NodeID child = nodeCollection().addNode();
        try {
            moveSubtree(child, parent, position, relation);
        } catch (IllegalCycleException ex) {
            // This should never happen!
            throw new InconsistentViewException(
                    "Unexpected illegal cycle when adding new node", ex);
        }
        
        // Return child node
        return child;
    }

    @Override
    public int leftChildren(NodeID parent) {
        int children = 0;
        NodeID child = innerLeftChild(parent);
        while (child != null) {
            ++children;
            child = leftSibling(child);
        }
        return children;
    }
    
    @Override
    public int rightChildren(NodeID parent) {
        int children = 0;
        NodeID child = outerRightChild(parent);
        while (child != null) {
            ++children;
            child = leftSibling(child);
        }
        return children;        
    }
    
    @Override
    public NodeID leftSibling(NodeID node) {
        return graph().outNode(firstEdgeMatch(graph().inEdges(node, siblingLayer), 
                RelationNextLeftField, RelationNextRightField));
    }

    @Override
    public NodeID rightSibling(NodeID node) {
        return graph().inNode(firstEdgeMatch(graph().outEdges(node, siblingLayer), 
                RelationNextLeftField, RelationNextRightField));
    }

    @Override
    public NodeID innerSibling(NodeID node) {
        NodeID innerSibling = graph().outNode(
                firstEdgeMatch(graph().inEdges(node, siblingLayer),
                    RelationNextRightField));
        if (innerSibling == null)
            innerSibling = graph().inNode(
                firstEdgeMatch(graph().outEdges(node, siblingLayer),
                    RelationNextLeftField));
        return innerSibling;
    }
    
    @Override
    public NodeID outerSibling(NodeID node) {
        NodeID outerSibling = graph().inNode(
                firstEdgeMatch(graph().outEdges(node, siblingLayer),
                    RelationNextRightField));
        if (outerSibling == null)
            outerSibling = graph().outNode(
                firstEdgeMatch(graph().inEdges(node, siblingLayer),
                    RelationNextLeftField));
        return outerSibling;
    }
    
    @Override
    public NodeID outerLeftChild(NodeID parent) {
        return graph().inNode(firstEdgeMatch(graph().outEdges(parent, siblingLayer), 
                RelationOuterLeftChild));
    }

    @Override
    public NodeID innerLeftChild(NodeID parent) {
        return graph().inNode(firstEdgeMatch(graph().outEdges(parent, siblingLayer), 
                RelationInnerLeftChild));
    }

    @Override
    public NodeID innerRightChild(NodeID parent) {
        return graph().inNode(firstEdgeMatch(graph().outEdges(parent, siblingLayer), 
                RelationInnerRightChild));
    }

    @Override
    public NodeID outerRightChild(NodeID parent) {
        return graph().inNode(firstEdgeMatch(graph().outEdges(parent, siblingLayer),
            RelationOuterRightChild));
    }

    @Override
    public boolean inLeftField(NodeID child) {
        return null != firstEdgeMatch(graph().inEdges(child, siblingLayer), 
            RelationNextLeftField, RelationOuterLeftChild, RelationInnerLeftChild);
    }

    @Override
    public boolean inRightField(NodeID child) {
        return null != firstEdgeMatch(graph().inEdges(child, siblingLayer), 
                RelationNextRightField, RelationOuterRightChild, RelationInnerRightChild);
    }
    
    @Override
    public NodeID leftBoundary(NodeID node) {
        NodeID boundary = node;
        NodeID outerLeftChild;
        while ((outerLeftChild = outerLeftChild(boundary)) != null)
            boundary = outerLeftChild;
        return boundary;
    }

    @Override
    public NodeID rightBoundary(NodeID node) {
        NodeID boundary = node;
        NodeID outerRightChild;
        while ((outerRightChild = outerRightChild(boundary)) != null)
            boundary = outerRightChild;
        return boundary;
    }

    @Override
    public NodeID left(NodeID node) {
        // Return right boundary of inner left child, if it exists
        NodeID child = innerLeftChild(node);
        if (child != null) 
            return rightBoundary(child);
        
        // Go up to the lowest transitive sibling/parent that precedes this node,
        // then return the parent or the right boundary of the sibling
        NodeID upper = node; 
        while (true) {
            // Give up when we reach top node
            if (upper == null || upper == top())
                return null;
            
            // Check whether upper has left child
            // Check whether upper has left sibling
            NodeID sibling = leftSibling(upper);
            if (sibling != null)
                return rightBoundary(sibling);
            
            // Check whether upper is an inner right child
            NodeID parent = graph().outNode(firstEdgeMatch(graph().inEdges(upper, siblingLayer), 
                    RelationInnerRightChild));
            if (parent != null && parent != top())
                return parent;
            
            // Otherwise move to parent
            upper = parent(parentEdge(upper));
        }
    }

    @Override
    public NodeID right(NodeID node) {
        // Return left boundary of inner right child, if it exists
        NodeID child = innerRightChild(node);
        if (child != null) 
            return leftBoundary(child);
        
        // Go up to the lowest transitive sibling/parent that succeeds this node,
        // then return the parent or the left boundary of the sibling
        NodeID upper = node; 
        while (true) {
            // Give up when we reach top node
            if (upper == null || upper == top())
                return null;
            
            // Check whether upper has right sibling
            NodeID sibling = rightSibling(upper);
            if (sibling != null)
                return leftBoundary(sibling);
            
            // Check whether upper is an inner left child
            NodeID parent = graph().outNode(firstEdgeMatch(graph().inEdges(upper, siblingLayer), 
                    RelationInnerLeftChild));
            if (parent != null && parent != top())
                return parent;
            
            // Otherwise move to parent
            upper = parent(parentEdge(upper));
        }
    }
   
    @Override
    public EdgeID roof(NodeID node) {
        // The roof is a parent edge or a sibling edge to the 
        // highest left or right periphery parent (whichever is highest)
        NodeID highestPeripheryParent = highestPeripheryParent(node);
        if (highestPeripheryParent == node) {
            // Return outer sibling edge if it exists
            NodeID outerSibling = outerSibling(node);
            return (outerSibling != null) ? parentEdge(outerSibling) : null;
        }
        
        // Determine whether node is on the left/right of its highest 
        // periphery parent
        boolean rightPeriphery = inRightField(node);
        
        // Find roof edge from highest periphery parent
        if (rightPeriphery) {
            // Node is on the right periphery of its highest periphery parent
            if (inLeftField(highestPeripheryParent))
                // highest periphery parent is in the left field of its parent
                return parentEdge(highestPeripheryParent);
            
            // Look for right sibling
            NodeID rightSibling = rightSibling(highestPeripheryParent);
            if (rightSibling != null)
                return parentEdge(rightSibling);
        } else {
            // Node is on the left periphery of its highest periphery parent
            if (inRightField(highestPeripheryParent))
                // highest periphery parent is in the right field of its parent
                return parentEdge(highestPeripheryParent);
            
            // Look for right sibling
            NodeID leftSibling = leftSibling(highestPeripheryParent);
            if (leftSibling != null)
                return parentEdge(leftSibling);
        }

        // No roof was found: return null
        return null;
    }
    
    @Override
    public int position(final NodeID node) {
        // Check whether node is in left field or in right field (return 0 if
        // contained in neither field)
        boolean inLeftField = inLeftField(node);
        if (! (inLeftField || inRightField(node)))
            return 0;
        
        // Move along inner siblings to head node, keeping track of position
        int position = 0;
        NodeID hare = node;
        if (inLeftField) {
            while (hare != null) {
                hare = rightSibling(hare);
                --position;
            }
        } else {
            // Right field
            while (hare != null) {
                hare = leftSibling(hare);
                ++position;
            }
        }
        
        // Return position
        return position;
    }
    
    @Override
    public List<NodeID> leftPeriphery(NodeID node) {
        List<NodeID> leftPeriphery = new ArrayList<NodeID>();
        NodeID hare = node;
        while (hare != null) {
            leftPeriphery.add(hare);
            hare = outerLeftChild(hare);
        }
        return Arrays.asList(leftPeriphery.toArray(new NodeID[0]));
    }

    @Override
    public List<NodeID> rightPeriphery(NodeID node) {
        List<NodeID> rightPeriphery = new ArrayList<NodeID>();
        NodeID hare = node;
        while (hare != null) {
            rightPeriphery.add(hare);
            hare = outerRightChild(hare);
        }
        return Arrays.asList(rightPeriphery.toArray(new NodeID[0]));
    }

    @Override
    public NodeID highestLeftPeripheryParent(NodeID node) {
        NodeID hare = node;
        NodeID parent = parent(parentEdge(hare));
        while (parent != null && hare == outerLeftChild(parent)) {
            hare = parent;
            parent = parent(parentEdge(hare));
        }
        return hare;
    }
    
    @Override
    public NodeID highestRightPeripheryParent(NodeID node) {
        NodeID hare = node;
        NodeID parent = parent(parentEdge(hare));
        while (parent != null && hare == outerRightChild(parent)) {
            hare = parent;
            parent = parent(parentEdge(hare));
        }
        return hare;
    }
    
    @Override
    public NodeID highestPeripheryParent(NodeID node) {
        NodeID highestPeripheryParent = highestRightPeripheryParent(node);
        if (highestPeripheryParent == node) {
            // Nope, the node was to the left of its parent
            highestPeripheryParent = highestLeftPeripheryParent(node);
        }
        return highestPeripheryParent;
    }
    
    /**
     * The following rules are used to compute the position for the new site:
     * 
     *     1. position=old position at old parent
     *         site == old parent
     * 
     *     2. position=position on the inside of the roof child
     *         site == roof parent
     * 
     *     3. position=outer left position
     *         (a) site is left && highest parent == inner sibling of node, or
     *         (b) no roof && node is left && highest parent == top, or
     *         (c) site == right roof child, or
     *         (d) site != roof node && site is left && highest parent == right roof node, or
     * 
     *     4. position=outer right position
     *         (a) site is right && highest parent == inner sibling of node, or
     *         (b) no roof && node is right && highest parent == top, or
     *         (c) site == left roof child, or
     *         (d) site != roof node && site is right && highest parent == left roof node
     * 
     *     5. position=0
     *         all other cases
     **/
    @Override
    public int projectiveParentSite(NodeID node, NodeID site) {
        // 0. Return 0 if node equals site, or node or site is null
        NodeID parent = parent(parentEdge(node));
        if (node == site || parent == null || site == null)
            return 0;
        
        // 1. Return old position if site is old parent
        if (site == parent) 
            return position(node);
        
        // Find the highest periphery parent of the new site, and the inner sibling
        // of the node
        boolean nodeInLeftField = inLeftField(node);
        boolean siteInLeftField = inLeftField(site);
        NodeID innerSibling = innerSibling(node);
        NodeID highestPeripheryParentForSite = highestPeripheryParent(site);
        
        // 3a+4a. Is the highest periphery parent for site equal to the inner sibling? 
        if (highestPeripheryParentForSite == innerSibling && nodeInLeftField == siteInLeftField)
            return siteInLeftField 
                    ? leftChildren(site) - 1
                    : rightChildren(site) + 1;
        
        // Find the roof of the node
        NodeID roofParent, roofChild, roofLeft, roofRight;
        EdgeID roof = roof(node);
        if (roof != null) {
            roofParent = parent(roof);
            roofChild = child(roof);
            if (inLeftField(roofChild)) {
                roofLeft = roofChild;
                roofRight = roofParent;
            } else {
                roofLeft = roofParent;
                roofRight = roofChild;
            }            
        } else {
            roofParent = roofChild = roofLeft = roofRight = null;
        }

        // 2. Site == roof parent?
        if (site == roofParent)
            return position(roofChild);
            
        // 3. Position = outer left
        NodeID highestPeripheryParent = highestPeripheryParent(node);
        if (    // 3b
                (roof == null && nodeInLeftField && highestPeripheryParentForSite == top()
                    && ! dominates(node, site)) ||
                // 3c
                (site == roofRight && site == roofChild) ||
                // 3d
                (highestPeripheryParentForSite == roofRight && siteInLeftField 
                    && site != roofChild && site != roofParent 
                    && roofRight != roofParent)) {
            return - leftChildren(site) - 1;
        }
        
        // 4. Position = outer right
        if (    // 4b
                (roof == null && (! nodeInLeftField) && highestPeripheryParentForSite == top()
                    && ! dominates(node, site)) ||
                // 4c
                (site == roofLeft && site == roofChild) ||
                // 4d
                (highestPeripheryParentForSite == roofLeft && (! siteInLeftField) 
                    && site != roofChild && site != roofParent && roofLeft != roofParent)) {
            return rightChildren(site) + 1;
        }
       
        // 5. Position = 0
        return 0;
    }
    
    @Override
    public List<LandingSite> projectiveParentSites(NodeID node) {
        List<LandingSite> parentSites = new ArrayList<LandingSite>();

        // Find node's parent
        NodeID parent = parent(parentEdge(node));
        if (parent == null)
            return Arrays.asList(new LandingSite[0]);

        // Find node's direction, inner sibling, and roof
        boolean nodeInLeftField = inLeftField(node);
        NodeID innerSibling = innerSibling(node);
        NodeID roofParent, roofChild, roofLeft, roofRight;
        EdgeID roof = roof(node);
        if (roof != null) {
            roofParent = parent(roof);
            roofChild = child(roof);
            if (inLeftField(roofChild)) {
                roofLeft = roofChild;
                roofRight = roofParent;
            } else {
                roofLeft = roofParent;
                roofRight = roofChild;
            }            
        } else {
            roofParent = roofChild = roofLeft = roofRight = null;
            if (nodeInLeftField)
                roofChild = roofRight = top();
            if (! nodeInLeftField)
                roofChild = roofLeft = top();
        }
        
        // Find inner sibling of roof child in graph where node has been removed
        NodeID innerSiblingRoofChild = innerSibling(roofChild);
        if (innerSiblingRoofChild == node)
            innerSiblingRoofChild = innerSibling(node);
            
        // Find left and right periphery root
        NodeID peripheryLeft = roofLeft;
        NodeID peripheryRight = roofRight;
        if (roof == null) {
            // There is no roof
            if (nodeInLeftField)
                peripheryRight = top();
            if (! nodeInLeftField)
                peripheryLeft = top();
        } else {
            // There is a roof
            if (roofLeft == roofParent) {
                peripheryLeft = innerSiblingRoofChild;
            } else {
                peripheryRight = innerSiblingRoofChild;
            }
        }
        
        // Left parents above and below parent, but below roofParent
        List<NodeID> leftParents = new ArrayList<NodeID>();
        if (roofLeft != null) {
            List<NodeID> rightPeriphery = rightPeriphery(peripheryLeft);
            int i = rightPeriphery.indexOf(node);
            if (i >= 0)
                rightPeriphery = rightPeriphery.subList(0, i);
            leftParents.addAll(rightPeriphery);
        }
        if (innerSibling != null && ! nodeInLeftField && innerSibling != peripheryLeft)
            leftParents.addAll(rightPeriphery(innerSibling)); 
        for (NodeID leftParent : leftParents) {
            if (leftParent != parent) {
                parentSites.add(new LandingSite(leftParent, rightChildren(leftParent) + 1));
            } else {
                parentSites.add(new LandingSite(leftParent, position(node)));
            }
        }
        
        // Add roof parent
        if (roof != null)
            parentSites.add(new LandingSite(roofParent, 
                    (roofParent == parent) ? position(node) : position(roofChild)));
                
        // Right parents above and below parent, but below roofParent
        List<NodeID> rightParents = new ArrayList<NodeID>();
        if (roofRight != null) {
            List<NodeID> leftPeriphery = leftPeriphery(peripheryRight);
            int i = leftPeriphery.indexOf(node);
            if (i >= 0)
                leftPeriphery = leftPeriphery.subList(0, i);
            rightParents.addAll(leftPeriphery);            
        }
        if (innerSibling != null && nodeInLeftField && innerSibling != peripheryRight)
            rightParents.addAll(leftPeriphery(innerSibling));
        for (NodeID rightParent : rightParents) {
            if (rightParent != parent) {
                parentSites.add(new LandingSite(rightParent, - (leftChildren(rightParent) + 1)));
            } else {
                parentSites.add(new LandingSite(rightParent, position(node)));
            }
        }
        
        // Return entire list
        return Arrays.asList(parentSites.toArray(new LandingSite[0]));
    }

    @Override
    public NodeID lowestLeftTransitiveParent(NodeID node) {
        NodeID hare = node;
        while (hare != null) {
            if (inRightField(hare))
                return parent(parentEdge(hare));
            hare = parent(parentEdge(hare));
        }
        return null;
    }

    @Override
    public void clear() {
        super.clear();
        graph().clear(siblingLayer);
    }

    List<EdgeID> edgeMatches(List<EdgeID> edges, Object... relations) {
        List<EdgeID> matches = new ArrayList<EdgeID>();
        for (EdgeID edge : edges)
            for (Object relation : relations)
                if (relation(edge) == relation)
                    matches.add(edge);
        return Arrays.asList(matches.toArray(new EdgeID[0]));
    }
    
    EdgeID firstEdgeMatch(List<EdgeID> edges, Object... relations) {
        // Return first matching in-edge with one of the given edge relations
        // in the given layer
        for (EdgeID edge : edges)
            for (Object relation : relations)
                if (relation(edge) == relation)
                    return edge;
        
        // Return null otherwise
        return null;
    }
    
    EdgeID addSiblingEdge(NodeID node, NodeID parent, Object relation)
            throws NodeNotFoundException {
        try {
            EdgeID edge = graph().addEdge(node, parent, siblingLayer);
            setRelation(edge, relation);
            return edge;
        } catch (LocationNotFoundException ex) {
            throw new InconsistentGraphException(
                    "Cannot find edge returned by graph itself with addEdge", ex);
        }
    }
    
    // Unlink node from its parent and its siblings in the siblings layer
    void unlinkFromSiblings(NodeID node) {
        // Find left and right sibling
        NodeID leftSibling = null;
        NodeID rightSibling = null; 
        NodeID parent = null;
        Object nextRelation = null;
        boolean outerLeftChild = false;
        boolean innerLeftChild = false;
        boolean innerRightChild = false;
        boolean outerRightChild = false;
        
        // Delete all existing in-edges in sibling layer
        for (EdgeID edge : graph().inEdges(node, siblingLayer)) {
            Object relation = relation(edge);
            if (RelationNextLeftField.equals(relation) || RelationNextRightField.equals(relation)) {
                leftSibling = graph().outNode(edge);
                nextRelation = relation;
            } else if (RelationOuterLeftChild.equals(relation)) {
                outerLeftChild = true;
                parent = graph().outNode(edge);
            } else if (RelationInnerLeftChild.equals(relation)) {
                innerLeftChild = true;
                parent = graph().outNode(edge);
            } else if (RelationInnerRightChild.equals(relation)) {
                innerRightChild = true;
                parent = graph().outNode(edge);
            } else if (RelationOuterRightChild.equals(relation)) {
                outerRightChild = true;
                parent = graph().outNode(edge);
            } else {
                // Unknown edge: do not remove
                continue;
            }
            graph().removeEdge(edge);
        }
        
        // Delete all next out-edges in sibling layer
        for (EdgeID edge : graph().outEdges(node)) {
            Object relation = relation(edge);
            if (relation == RelationNextLeftField || relation == RelationNextRightField) {
                rightSibling = graph().inNode(edge);
                nextRelation = relation(edge);
                graph().removeEdge(edge);
            }
        }
       
        // Create new edges
        try {
            if (leftSibling != null && rightSibling != null)
                addSiblingEdge(rightSibling, leftSibling, nextRelation);
            if (outerLeftChild && rightSibling != null)
                addSiblingEdge(rightSibling, parent, RelationOuterLeftChild);
            if (innerLeftChild && leftSibling != null)
                addSiblingEdge(leftSibling, parent, RelationInnerLeftChild);
            if (innerRightChild && rightSibling != null)
                addSiblingEdge(rightSibling, parent, RelationInnerRightChild);
            if (outerRightChild && leftSibling != null)
                addSiblingEdge(leftSibling, parent, RelationOuterRightChild);
        } catch (NodeNotFoundException ex) {
            throw new InconsistentGraphException("Cannot find node returned" +
                    " by graph itself", ex);
        }
    }

    @Override
    public ProjectiveTreeEngine copy() {
        NodeCollection nodeCollectionCopy = (NodeCollection) nodeCollection().copy();
        return new ProjectiveTreeEngine(graph(), nodeCollectionCopy, top(), treeLayer(), siblingLayer);
    }
    
    @Override
    public void setGraph(final Graph graph) {
        // First check that new graph is compatible with the projective tree
        if (! graph.containsLayer(siblingLayer)) 
            throw new InconsistentViewException("Cannot set new graph in ProjectiveTreeEngine:" +
                    " sibling layer is not contained in graph");
        
        // Then try to change the graph as a tree using super class method
        super.setGraph(graph);
    }
   
    @Override
    public List<NodeID> subnodesInOrder(NodeID node) {
        return subnodesInOrder(node, new ArrayList<NodeID>());
    }

    private List<NodeID> subnodesInOrder(NodeID node, List<NodeID> subnodes) {        
        // Visit left children
        NodeID child = outerLeftChild(node);
        while (child != null) {
            subnodesInOrder(child, subnodes);
            child = rightSibling(child);
        }
        
        // Visit node
        subnodes.add(node);
        
        // Visit right children
        child = innerRightChild(node);
        while (child != null) {
            subnodesInOrder(child, subnodes);
            child = rightSibling(child);
        }
        
        return subnodes;
    }
    
    
    // 1=view ID, 3=node collection, 5=top node, 7=tree layer, 9=sibling layer
    private static final Pattern osdtProjectiveTreeEnginePattern = Pattern.compile(
            "^\\s*VIEW([0-9]+)\\s+ProjectiveTreeEngine\\((VIEW)?([0-9]+),(NODE)?([0-9]+)," 
            + "(LAYER)?([0-9]+),(LAYER)?([0-9]+)\\)\\s*$");    

    @Override
    public String toOSDT(Graph graph, GraphIDs ids) {
        return "ProjectiveTreeEngine(VIEW" + ids.id(nodeCollection()) + ","
                + "NODE" + ids.id(top()) + ","
                + "LAYER" + ids.id(treeLayer()) + ","
                + "LAYER" + ids.id(siblingLayer) + ")";
    }

    public static ProjectiveTreeEngine fromOSDT(Graph graph, GraphIDs ids, String osdt)
            throws OsdtSyntaxException {
        // Parse OSDT string
        Matcher m = osdtProjectiveTreeEnginePattern.matcher(osdt);
        if (! m.find())
            return null;
        
        // Find source and target node collections, and alignment layer
        try {
            // Find view ID, node collection, top node, and tree layer
            int viewID = Integer.parseInt(m.group(1));
            NodeCollection nodeCollection 
                    = (NodeCollection) ids.getView(Integer.parseInt(m.group(3)));
            NodeID top = ids.getNode(Integer.parseInt(m.group(5)));
            Layer treeLayer = ids.getLayer(Integer.parseInt(m.group(7)));
            Layer siblingLayer = ids.getLayer(Integer.parseInt(m.group(9)));
            
            // Create new tree engine
            return new ProjectiveTreeEngine(graph, 
                    nodeCollection, top, treeLayer, siblingLayer);
        } catch (Exception ex) {
            throw new OsdtSyntaxException("Cannot find view or layer in OSDT string: " + osdt);
        }
    }

    @Override
    public void recompute() {
        // TODO
        // throw new UnsupportedOperationException("Not yet implemented");
    }

}
